#include <iostream>
using namespace std;

struct student
{
	char name[20];
	int score;
	struct student *next;
};

typedef student NODE;

// Search 查找关键字小于 key 的结点的前驱
NODE *Search(NODE *head, int key)
{
	NODE *p;
	p = head;
	while (p->next != NULL)
	{
		if (p->next->score < key)
			return p;
		p = p->next;
	}
	return p;
}

// InsertNode 在 p 之后插入结点 newp
void InsertNode(NODE *p, NODE *newp)
{
	newp->next = p->next;
	p->next = newp;
}

// DelNode 删除 p 结点的一个后继结点
void DelNode(NODE *p)
{
	if (p->next != NULL)
	{
		NODE *q = p->next;
		p->next = q->next;
		delete q;
	}
}

// DelList 销毁整个链表
void DelList(NODE *head)
{
	NODE *p;
	p = head;
	while (head->next != NULL)
	{
		head = head->next;
		delete p;
		p = head;
	}
	delete head;
}

// DispList 显示链表各元素
void DispList(NODE *head)
{
	NODE *p;
	p = head;
	while (p->next != NULL)
	{
		cout << p->next->name << "\t" << p->next->score << endl;
		p = p->next;
	}
}

int main()
{
	cout << endl
		 << "学号：3170608043，姓名：石英钰" << endl
		 << endl
		 << "p134【例3-14】单向链表的排序、查找、插入、删除" << endl
		 << endl;
	NODE *newp, *head, *p;
	char name[20];
	int score, low = 60;
	if ((newp = new NODE) == NULL)
	{
		cout << "new NODE fail!" << endl;
		exit(0);
	}
	head = newp;
	head->next = NULL;
	cout << "Input name and score(-1 to exit):" << endl;
	cin >> name >> score;
	while (score > 0)
	{
		if ((newp = new NODE) == NULL)
		{
			cout << "new NODE fail!" << endl;
			exit(0);
		}
		strcpy(newp->name, name);
		newp->score = score;
		newp->next = NULL;
		p = Search(head, score);
		InsertNode(p, newp);
		cin >> name >> score;
	}
	cout << "Before delete:" << endl;
	DispList(head);
	for (p = Search(head, low); p->next != NULL; p = Search(head, low))
		DelNode(p);
	cout << "After detele:" << endl;
	DispList(head);
	DelList(head);
	return 0;
}